#include <iostream>
#include <vector>
#include <algorithm>  // 用于std::swap（虽然这里没用到）

using namespace std;

// 模板函数，支持任何可比较的数据类型
template<typename T>
void binaryInsertionSort(vector<T>& arr) {
    int n = arr.size();
    
    for (int i = 1; i < n; i++) {
        T key = arr[i];  // 当前要插入的元素
        
        // 使用二分查找找到插入位置
        int low = 0;
        int high = i - 1;
        
        while (low <= high) {
            int mid = low + (high - low) / 2;  // 防止溢出
            if (arr[mid] > key) {
                high = mid - 1;  // 在左半部分继续查找
            } else {
                low = mid + 1;   // 在右半部分继续查找
            }
        }
        
        // 将元素向后移动，为插入腾出空间
        for (int j = i - 1; j >= low; j--) {
            arr[j + 1] = arr[j];
        }
        
        // 插入元素到正确位置
        arr[low] = key;
    }
}

// 重载函数，支持数组和大小参数
template<typename T>
void binaryInsertionSort(T arr[], int n) {
    for (int i = 1; i < n; i++) {
        T key = arr[i];
        int low = 0;
        int high = i - 1;
        
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] > key) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        
        for (int j = i - 1; j >= low; j--) {
            arr[j + 1] = arr[j];
        }
        
        arr[low] = key;
    }
}

// 打印vector
template<typename T>
void printVector(const vector<T>& arr) {
    for (const auto& elem : arr) {
        cout << elem << " ";
    }
    cout << endl;
}

// 打印数组
template<typename T>
void printArray(T arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    // 测试vector版本
    vector<int> vec = {64, 34, 25, 12, 22, 11, 90};
    cout << "原始vector: ";
    printVector(vec);
    
    binaryInsertionSort(vec);
    cout << "排序后vector: ";
    printVector(vec);
    
    cout << "------------------------" << endl;
    
    // 测试数组版本
    int arr[] = {9, 5, 1, 4, 3, 8, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    cout << "原始数组: ";
    printArray(arr, n);
    
    binaryInsertionSort(arr, n);
    cout << "排序后数组: ";
    printArray(arr, n);
    
    return 0;
}
